The emerging use of low-rate coding and digital transmission in mobile satellite communications and the increasing use of facsimile services have identified the desirability for visual service transparency over the same very narrow-band circuits. The economic viability of such a service, however, rests on the capability of introducing further image message compression, either in real-time or off-line during a so-called store-and-forward operation. In addition to the economic side, however, long document transmission times negatively impact the customer perceived quality of service in that, over narrow-band circuits, several minutes might be required for the transmission of documents that would normally need only seconds when transmitted through the public switch telephone network. In order to achieve these objectives, some form of image compression over and above what is provided by traditional Group 3 facsimile is needed.
Of general interest are U.S. Pat. No. 4,779,266 to Chung et al., which discloses methods and corresponding circuitry for encoding and decoding information with code patterns which engender the two-state equivalent of electronic orthogonal coding. These special code patterns, referred to as optimizing orthogonal codes, are useful in system having only two signal propagation states, e.g., optical processors and U.S. Pat. No. 4,695,971 to Reimann, which discloses circuitry for rapidly determining the greatest difference among three binary numerical values which undertakes a classification and coding of the maximum difference within a number of different numerical ranges.
References of limited interest include U.S. Pat. No. 3,971,88 to Ching et al., which discloses a synchronization system for variable length encoded signals, U.S. Pat. No. 3,938,085 to Battail, which discloses a transmission system including a transmitting station and a receiving station for operating with a systematic recurrent code, and U.S. Pat. No. 3,927,372 to Zschunke, which discloses techniques for improving the reproduction of amplitude jumps in a differential pulse code modulation (DPCM) system based on the use of maximum difference value code words.
Currently there are several methods in use for encoding bi-level graphics. These include:
a. One-dimensional Huffman Coding, which is used to encode colored (black or white) strips of picture elements (pixels) when an image is raster-scanned and digitized. A well known algorithm belonging to this class of techniques is the 1-Dimensional Run-Length Coding (RLC) which has become an international standard. See CCITT Recommendation T.4., "Standardization of Group 3 Facsimile Apparatus for Document Transmissions", Melbourne 1988, Fascicle VI1.3 Volume VII, Pages 21-47. The 1-Dimensional RLC consists of a Huffman Code that has been suitably modified to increase its robustness in the presence of telephone network-type of impairments. The 1-Dimensional RLC is a powerful technique that permits the lossless coding of bi-level images and is able to achieve a bit-rate requirement reduction on the order of 10:1, depending on the statistical content of the image encoded. However, since group 3 facsimile messages are already encoded using this technique there can be little, if any, benefit derived by further compressing such images in the network using the same, or a modified version of this approach.
b. To increase the compression achievable, a two dimensional version of the 1-Dimensional RLC technique has also been developed. See CCITT Recommendation T.4. In the 2-Dimensional RLC method, only the first scan-line of image information is encoded in accordance to the 1-Dimensional RLC. Subsequently, the differences between adjacent lines, rather than the actual scan-lines, are encoded using a technique that is essentially the same as 1-Dimensional RLC. The 2-Dimensional RLC is also a loss-less coding method. However, because of its increased image redundancy removal, it is more susceptible to telephone network-type of transmission impairments. As a result, 1-Dimensional RLC of the actual scan-lines is used every few lines to assure that re-synchronization can be established even when some of the encoded information has been corrupted. As a result, its performance is somewhat limited. Furthermore, since, as stated earlier, group 3 facsimile messages are already encoded using this standardized technique, there can be little additional benefit realized, e.g., an additional 20%, by further compressing such images in the network using a 2-dimensional Huffman coding approach, or a variant thereof.
c. If the communications channel can be assumed to be error free, e.g., when automatic repeat request procedures are employed, a slightly more efficient method of 2-D RLC can be derived. In this method, all image scan-lines are coded on an adjacent line differential basis and 1-Dimensional RLC is not repeated for re-synchronization. This method is somewhat more efficient in that a compression ratios of the order of 20:1 can be achieved. However, the underlying error-free channel assumption is noted. This method has also been standardized, and is covered by, for example, CCITT Recommendation T.6, entitled "Facsimile Coding Schemes and Coding Control Functions for Group 4 Facsimile Apparatus" (Melbourne 1988, Fascicle VII.3, Volume VII).
d. Other techniques for the coding of facsimile images have also been used. See K. Knowlton, "Progressive Transmission of Gray-Scale and Binary Images by Simple, Efficient and Lossless Coding Scheme", Proceedings of IEEE, pp. 885-896 (July 1980), and N. S Jayant et al., "Digital Coding of Waveforms", Prentice Hall (1984). Some of these employ transform domain techniques and promise to be effective, but primarily only when dealing with graphical information such as gray level, or highly detailed images. As a result, such methods have not demonstrated their optimal abilities when coding bi-level handwritten graphics for mobile communication applications.
e. Another technique which has proven to be powerful is based on the segmentation of an image into many sub-images and in subsequently matching the content of these sub-images by elements drawn from a code-book of elementary images. The process is completed by transmitting over the communications channel a code-word representing the identity of the elementary image most closely resembling the image's sub-image. Such techniques combine pattern recognition principles and vector quantization and have demonstrated that significant compression ratios can be achieved, e.g., more that 100:1, if the code-book used is well suited to the image contention a microscope scale). See O. Johnsen et al., "Coding of Two-Level Pictures by Pattern Matching and Substitution", The Bell System Technical Journal, Vol. 62, No. 8, pp. 2513-2545 (October 1983) as well as Super Fax Compression, COMSAT Laboratories Final Report under Contract MCS-10 (December 1991). Despite the impressive compression ability of these techniques, some limitations should be noted when the image structure is not well matched to the codebook contents. First, the compression ratios realized are significantly lower than 100:1. Second, these techniques are information lossy, i.e., the reconstructed image quality is degraded when compared to the original image. In particular, if the image structure is not well matched to the codebook's contents, the reconstructed image quality can be significantly degraded. As a result, the performance of these techniques is essentially limited to compression ratios in the range of 40:1 to 100:1 and their use can be primarily confined to typed text, where the outline of the characters to be coded is well defined and uniform throughout a document.
f. A technique called Vector Encoding with a Distortion Criterion (VEDC), was proposed but not disclosed by COMSAT Corporation employees which models each character within an image as a short sequence of interlocked 2-dimensional vectors whose lengths and directions are coded using variable length Huffman coding. The coding process is completed when a location is provided for the origin of the first vector associated with each character. This technique has the ability to efficiently encode line graphics, as well as handwritten or typed text, while maintaining a constant level of distortion across the encoded page. This method is primarily geared towards the so-called store-and-forward operation, rather than real-time operations, or else the full compression efficiency benefits can not be realized.
g. Finally, a set of techniques known as "Maximum Differences" and "Analysis-by-Synthesis" have been proposed. See commonly-assigned U.S. Pat. No. 5,293,251, which is incorporated herein by reference for all purposes. See also the articles by Spiros Dimolitsas and Franklin L. Corcoran, co-inventors of U.S. Pat. No. 5,293,251, entitled "Facsimile Compression for Transmission over 800 bit/s to 2400 bit/s Digital Mobile Circuits", Conference Proceedings, IEEE Military Communications Conference, MILCOM '90, Monterey, Calif., and "Compression of Facsimile Graphics for Transmission over Digital Mobile Satellite Channels", Conference Proceedings, IEEE Military Communications Conference, MILCOM '91, McLean, Va, pp. 644-647 (November 4-7, 1991).
The present invention was motivated by a desire to overcome the perceived problems in the techniques enumerated immediately above. For example, while the techniques described in U.S. Pat. No. 5,293,251 and the two MILCOM articles were suitable for the real-time network compression of facsimile images, it was not until the present invention was made that these techniques became usable, since these techniques not considered suitable for encoding either typed text or bi-level graphics which incorporated a significant amount of detail.